function quickSort(nums, left = 0, right = nums.length - 1) {
  if (left >= right) {
    return nums;
  }
  // 切分数组，返回基准元素的下标
  const pivotIndex = partition(nums, left, right);
  quickSort(nums, left, pivotIndex - 1);
  quickSort(nums, pivotIndex + 1, right);
  return nums;
}

function partition(nums, left, right) {
  // 选择区间里的随机元素作为基准
  const randomIndex = getRandomInt(left, right);
  [nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];

  const pivot = nums[left];

  let le = left + 1; // le: less equals
  let ge = right; // ge: greater equals
  // all in nums[left + 1 ... le) <= pivot
  // all in nums(ge ... right] >= pivot
  while (true) {
    while (le <= ge && nums[le] < pivot) {
      le++;
    }
    while (le <= ge && nums[ge] > pivot) {
      ge--;
    }
    // le 来到了第一个大于等于 pivot 的位置
    // ge 来到了第一个小于等于 pivot 的位置

    if (le >= ge) {
      break;
    }
    // 交换 nums[le] 和 nums[ge]
    [nums[le], nums[ge]] = [nums[ge], nums[le]];
    le++;
    ge--;
  }

  // 交换 nums[left] 和 nums[ge]
  [nums[left], nums[ge]] = [nums[ge], nums[left]];
  return ge;
}

// 返回 [min, max] 之间的随机整数
function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 测试用例
const testCases = [
  [],
  [1],
  [5, 3, 8, 4, 2],
  [10, 9, 8, 7, 6, 5],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3],
  [5, -1, 0, 2, -3, 8]
];

for (const arr of testCases) {
  console.log(`原数组: [${arr}] => 排序后: [${quickSort(arr)}]`);
}